1. Field of the Invention
The invention relates generally to communication systems and, more particularly, to multiple access protocols utilizing contention-based reservation.
2. Discussion of Related Art
In today's information age, there is an increasing need for high speed communications that provides guaranteed quality of service (QoS) for an ever-increasing number of communications consumers. To that end, communications networks and technologies are evolving to meet current and future demands. Specifically, new networks are being deployed which reach a larger number of end users, and protocols are being developed to utilize the added bandwidth of these networks efficiently.
One technology that has been widely employed and will remain important in the foreseeable future is the shared-medium network. A shared medium network is one in which a single communications channel (the shared channel) is shared by a number of end users such that uncoordinated transmissions from different end users may interfere with one another. In modern broadband communications networks, the shared communications channel is typically one of a number of frequency bands carried over a shared physical medium, such as a hybrid fiber-optic/coaxial cable (HFC) network or by electromagnetic waves in free space. Since communications networks typically have a limited number of communications channels, the shared medium network allows many end users to gain access to the network over a single communications channel, thereby allowing the remaining communications channels to be used for other purposes. However, the shared medium network is only feasible when each end user only transmits data intermittently, allowing other end users to transmit during periods of silence.
In the shared medium network, each end user interfaces to the shared channel by means of an Access Interface Unit (AIU) which allows the end user to transmit and receive information via the shared channel. A single AIU may support one or a number of end users. Each end user wishing to utilize the shared channel participates in a Medium Access Control (MAC) protocol which provides a set of rules and procedures for accessing the shared channel. For convenience, each participant in the MAC protocol is referred to as a MAC User.
One type of shared medium network utilizes a single headend unit for coordinating access by the MAC Users to the shared channel. The headend unit is typically situated at a common receiving end of the shared channel and is able to transmit messages to all MAC Users that share the channel. The headend unit coordinates access to the shared channel by sending control messages to the MAC Users which enable one or more MAC Users to transmit. MAC Users only transmit when enabled to do so by the headend unit.
FIG. 1 shows an exemplary shared medium network 100 as is known in the art. As illustrated in FIG. 1, a headend unit 110 is coupled to a plurality of AIUs 120.sub.a through 120.sub.n (collectively referred to as AIUs 120) via a shared channel 130. In the preferred embodiment, the shared channel 130 is one of a number of communications channels carried by a shared physical medium such as a hybrid fiber-optic/coaxial cable (HFC) or wireless network. In other embodiments, the shared physical medium may be coaxial cable, fiber-optic cable, twisted pair wires, and so on, and may also include air, atmosphere, or space for wireless and satellite communication. The headend unit 110 is also coupled to a communications network 140, which may include networks such as the Internet, on-line services, telephone and cable networks, and other communication systems.
Continuing to refer to FIG. 1, in the preferred embodiment, the shared physical medium, such as an HFC or wireless network, has or supports a plurality of communications channels. For ease of reference, the communications channels in which a headend unit, such as the headend unit 110, transmits information, signals, or other data to an AIU, such as AIU 120.sub.n, are referred to as downstream channels. Also for ease of reference, the communications channels in which an AIU, such as AIU 120.sub.n, transmits information, signals, or other data to a headend unit, such as headend unit 110, are referred to as upstream channels. These various upstream and downstream channels may, of course, be the same physical channel, for example, through time-division multiplexing and duplexing. They may also be separate physical channels, for example, through frequency-division multiplexing and duplexing. These various channels may also be logically divided in other ways, in addition to upstream and downstream directions. In the preferred embodiment, the communications medium is an HFC network, with downstream channels in the frequency spectrum (band) typically 50-750 MHz (and up to 1 GHz), and with upstream channels in the frequency spectrum typically 5-42 MHz.
In a simple model of an exemplary HFC network, the headend unit uses a single downstream channel to send information to a group of MAC Users, and a single upstream channel is used by all (or a number) of the group of MAC Users to send information to the headend unit. Since the headend unit is the only device which transmits on the downstream channel, the downstream channel is not a "shared channel" as that term is applied to the present invention. However, since multiple MAC Users transmit on the upstream channel, the upstream channel is a shared channel, and the MAC protocol must provide for orderly access to the channel so as to maximize the data throughput over the channel.
A number of different MAC protocols have been developed for use over a shared medium network. These protocols can generally be categorized as contention-free protocols, which avoid collisions on the shared channel by means of various scheduling methods, and contention-based protocols, which do not avoid collisions but instead resolve any collisions that do occur on the shared channel. Contention-free protocols, such as time-division multiple access (TDMA) and round-robin polling, are typically less efficient than contention-based protocols under light loads (i.e., many idle MAC Users) because the contention-free protocols generally allocate some amount of bandwidth to each MAC User whether or not the MAC User has information to send. On the other hand, contention-based protocols only allocate bandwidth to those MAC Users that have information to send, although some amount of bandwidth is wasted whenever collision resolution is required. Under heavy loads (i.e., many active MAC Users), there are likely to be many collisions. Thus, the effectiveness of a MAC protocol is generally dependent on the number of MAC Users as well as the amount of information they have to send.
One type of MAC protocol utilizes a reservation system in which each MAC User that wants to transmit data on the shared channel is required to make a reservation with the headend unit. Each MAC User that has data to transmit but has not already made a reservation waits for contention opportunities provided by the headend unit. Each contention opportunity is provided to a selected group of MAC Users, and allows each of the MAC Users in the specified group to contend for a reservation at a specific time provided it has data to send. For convenience, the term "data" is used generically to mean a collection of bits of information that may carry various forms of multimedia signals (e.g., voice, video, etc.).
In order to participate in the MAC protocol, each MAC User maintains a MAC User state machine as described in FIG. 2. The MAC User starts in the INACTIVE state 202, and remains there so long as it has no data to transmit. When the MAC User receives data to be transmitted, the MAC User transitions into the CONTENTION state 204. In the CONTENTION state 204, the MAC User contends for access to the channel until it is able to make a successful reservation for itself. Upon making a successful reservation in state 204, the MAC User transitions into the ACTIVE state 206. Here, the MAC User receives opportunities to transmit its data, and remains in the ACTIVE state 206 so long as it has data to transmit. Upon transmitting all of its data, the MAC User is considered to be "fulfilled," and the MAC User transitions back into the INACTIVE state 202.
For each contention opportunity provided by the headend unit, the headend unit receives either (1) no transmission, indicating that no MAC User transmitted a reservation request; (2) a reservation request, indicating that a single MAC User transmitted a reservation request and identifying that MAC User; or (3) a collision, indicating that more than one MAC User transmitted a reservation request. For convenience, the three feedback states are referred to as IDLE, SUCCESS, and COLLISION, respectively.
The headend unit schedules future contention opportunities and data transmission opportunities based on the result the contention-based reservation. If a successful reservation is made (i.e., if the result of the contention is SUCCESS), then the headend unit allocates bandwidth to the MAC User based on the QoS requirements of the corresponding end user so that the MAC User can transmit user information contention-free over the shared channel. On the other hand, if multiple MAC Users respond (i.e., if the result of the contention is COLLISION), then the headend unit attempts to aid in resolving the collision by providing additional contention opportunities.
The reservation-based MAC protocol can be represented at a high level by the state diagram shown in FIG. 3. The MAC protocol remains in the normal state 310 so long as the result of the contention-based reservation is IDLE or SUCCESS. The MAC protocol enters the collision resolution state 320 when the result of the contention-based reservation is COLLISION. In this state, a collision resolution procedure is employed to resolve the collision. Upon completion of the collision resolution procedure (i.e., all of the collisions, or a subset of them, are resolved), the MAC protocol returns to the normal state 310.
One technique for resolving collisions is called Probabilistic Tree Splitting (PTS). In the PTS technique, the contending MAC Users are divided into a number of probabilistically equal subsets by having each MAC User randomly select a subset. The headend unit then provides each subset with a separate contention opportunity. Each MAC User retransmits a reservation request only when its subset is provided with a contention opportunity. If a collision is detected for a particular subset, then the PTS technique is performed iteratively for the offending subset until all collisions have been resolved.
Each iteration of the PTS technique is associated with a collision resolution interval (CRI). The CRI defines a start time and an end time of an interval that contains the arrival times of individual messages of the MAC Users which are being considered for splitting. The start time marks a point in time that divides the arrival time of the oldest message pending successful reservation and the arrival times of all messages that have previously procured reservation. In transition to the next iteration, the CRI is updated by setting the start time of the new CRI equal to the end time of the previous CRI and setting the end time of the new CRI equal to the present time.
An example of the PTS model is shown in FIG. 4. The arrival times of individual messages 420.sub.1 through 420.sub.6 are represented as discrete points on the time line 410. Messages 420.sub.1 and 420.sub.2 are outside of the CRI 430, indicating that they had been handled by a previous reservation. Messages 420.sub.3 through 420.sub.6 are within the CRI, indicating that they have not yet been transmitted and are therefore eligible to contend in the normal state 310.
Upon detection of a collision within the CRI 430, the messages are split into two subsets 440 and 450. When the subset 440 is provided an opportunity to contend for a reservation, another collision will occur, since reservation requests for messages 420.sub.3, 420.sub.4, and 420.sub.6 will be transmitted. Thus, subset 440 will require additional iterations of PTS collision resolution. However, when the subset 450 is provided an opportunity to contend for a reservation, the reservation will be successful, since only a reservation request for message 420.sub.5 will be transmitted.
Another technique for resolving collisions is called First-Come-First-Served Splitting (FCFSS). In the FCFSS technique, the contending MAC Users are divided into subsets according to the arrival times of their messages. FCFSS is also an iterative technique applied to a CRI. The start time of the CRI marks a point in time that divides the arrival time of the oldest message pending successful reservation and the arrival times of all messages that have previously procured reservation.
When a collision is detected, the CRI is divided into two parts by time, so that there is an older time interval and a newer time interval. Collision resolution is first performed for the older time interval and, if no collisions remain in the older time interval, then for the newer time interval, by giving only those MAC Users having data with an arrival time within the particular time interval an opportunity to contend. If a collision is detected for either of those time intervals, then the FCFSS technique is performed iteratively for the offending time interval until an iteration is completed with no collisions in either the older time interval or the newer time interval.
An example of the FCFSS model is shown in FIG. 5. The arrival times of individual messages 520.sub.1 through 520.sub.6 are represented as discrete points on the time line 510. Messages 520.sub.1 and 520.sub.2 are outside of the Collision Resolution Interval 530, indicating that they had been handled by a previous reservation. Messages 520.sub.3 through 520.sub.6 are within the initial CRI, indicating that they have not yet been transmitted.
Upon detection of a collision within the CRI 530, the CRI is split into an older time interval 540 and a newer time interval 550. When the older time interval 540 is provided an opportunity to contend for a reservation, another collision will occur, since reservation requests for messages 520.sub.3 through 520.sub.5 will be transmitted. Thus, older time interval 540 will require at least one additional iteration of FCFSS collision resolution, initially using the older time interval 540 as the CRI. A contention opportunity for message 520.sub.6 will be provided during a subsequent CRI which minterval 550. be equal to the newer time interval 550.
The collision resolution procedure of the FCFSS technique can be conveniently described in terms of recursive logic. The logic is called recursive because it can invoke itself to resolve further collisions detected as the logic is executed, i.e. the collision resolution procedure is run anew from start to finish. Each iteration of the collision resolution procedure acts on a specified time interval T. When a collision is detected in the normal state of the MAC protocol, the collision resolution procedure is invoked with T equal to the CRI.
FIG. 6 shows one embodiment of FCFSS logic when the system enters the collision resolution state 320. The collision resolution logic begins in step 610, and proceeds to step 620 where it splits the time interval T into two sub-intervals, specifically an older time interval and a newer time interval. The logic then provides, in step 630, a contention opportunity for the older time interval. The logic then acts on the feedback state of the contention opportunity, in step 640. If the feedback state in step 640 is COLLISION, then the logic reinvokes the collision resolution procedure with T equal to the older time interval, in step 650, and terminates in step 699. However, if the feedback state in step 640 is IDLE or SUCCESS, then the logic proceeds to step 660 where it provides a contention opportunity for the newer time interval. The logic then acts on the feedback state of the contention opportunity, in step 670. If the feedback state in step 670 is COLLISION, then the logic reinvokes the collision resolution procedure with T equal to the newer time interval, in step 680, and terminates in step 699. However, if the feedback state in step 670 is SUCCESS, then the collision resolution procedure is considered to be complete, in step 690, and terminates in step 699.
FIG. 7 shows an improved embodiment of FCFSS logic when the system enters the collision resolution state 320. The improved collision resolution logic begins in step 710, and proceeds to step 720 where it splits the time interval T into two sub-intervals, specifically an older time interval and a newer time interval. The logic then provides, in step 730, a contention opportunity for the older time interval. The logic then acts on the feedback state of the contention opportunity, in step 740. If the feedback state in step 740 is COLLISION, then the logic reinvokes the collision resolution procedure with T equal to the older time interval, in step 750, and terminates in step 799. If the feedback state in step 740 is SUCCESS, then the logic proceeds to step 760 where it provides a contention opportunity for the newer time interval. The logic then acts on the feedback state of the contention opportunity, in step 770. If the feedback state in step 770 is COLLISION, then the logic reinvokes the collision resolution procedure with T equal to the newer time interval, in step 780, and terminates in step 799. However, if the feedback state in step 770 is SUCCESS, then the collision resolution procedure is considered to be complete, in step 790, and terminates in step 799. If the feedback state in step 740 is IDLE, indicating at least two contending messages in the newer interval, then the logic proceeds directly to step 780, where it reinvokes the collision resolution procedure with T equal to the newer time interval and terminates in step 799.
The improved embodiment described in FIG. 7 takes advantage of inherent state-based knowledge to predict the likelihood of future collisions and to react accordingly. Specifically, upon splitting the time interval T into an older time interval and a newer time interval and receiving an IDLE feedback state for the older time interval, a collision will occur for the newer time interval, in which case the collision resolution procedure would be reinvoked with T equal to the newer time interval. Therefore, instead of providing a contention opportunity for the newer time interval when an IDLE is detected for the older time interval, as in FIG. 6, the improved embodiment immediately reinvokes the collision resolution procedure with T equal to the newer time interval, thereby eliminating one contention cycle from the collision resolution procedure.
It should be noted that the collision resolution procedure for the FCFSS technique does not necessarily resolve all collisions from the original CRI. Instead, the collision resolution procedure resolves collisions for a sub-interval of the CRI which may or may not be equal to the CRI. Because the collision resolution procedure splits each time interval T into an older time interval and a newer time interval and attempts to resolve collisions in the older time interval first, the collision resolution procedure necessarily resolves collisions for a time period beginning at the start time of the original CRI and ending at the end time of the time interval T on which the collision resolution procedure completes. Thus, the collision resolution procedure allows the oldest data to be transmitted, possibly delaying the transmission of newer data until future contention opportunities. Upon completion of the collision resolution procedure, the CRI is advanced such that the start time of the new CRI is set equal to the end time of the time interval T (which represents the latest time before which all required reservations have been made), and the end time of the new CRI is set equal to the earlier of the present time and a point in time that is a predetermined increment from the start time of the CRI.
The performance of the FCFSS collision resolution technique is affected by the selection of the point for splitting the time interval T. It has been shown by Mosely and Humblet that the optimal point for splitting the time interval T for the FCFS algorithm is not the midpoint of the interval, but is in fact some time less than the midpoint (Mosely, J. and P. Humblet, "A Class of Efficient Contention Resolution Algorithms for Multiple Access Channels," IEEE Transactions on Communications, Vol. COM-33, No. 2, February 1985, pp. 145-151). However, the midpoint of the time interval T may be selected due to its ease of computation and near-optimal performance characteristics.
The PTS and FCFSS technique are known (for a general discussion, see Gallager, "A Perspective on Multiaccess Channels," IEEE Transactions on Information Theory, Vol. IT-31, No. 2, March 1985, pp. 124-142). While both techniques resolve collisions in generally the same manner (i.e., by dividing a number of contending MAC Users into smaller subsets in order to statistically improve the likelihood of success during subsequent contention opportunities), the FCFSS technique has an added advantage of favoring older data over newer data by allowing the "oldest" data (i.e. the data that has been queued the longest) to be transmitted ahead of "newer" data (hence the name "first-come-first-served"). Thus, the older data is given a higher priority relative to the newer data when a collision occurs.